package graphPath;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.jgrapht.WeightedGraph;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleWeightedGraph;

public class DeepFirstSearch {
	
	public int time;
	public Map <Integer, Integer> vertex_color;
	public Map <Integer, Integer> vertex_discover;
	public Map <Integer, Integer> vertex_finish;
	
	public DeepFirstSearch(){
		
		vertex_color = new HashMap<Integer, Integer>();
		vertex_discover = new HashMap<Integer, Integer>();
		vertex_finish = new HashMap<Integer, Integer>();
	}
	
	public void initial(WeightedGraph<String, DefaultWeightedEdge> graph){
		
		
		
		List<Integer> vertices = new ArrayList<Integer>();
		
		
		
		//set all vertex as white , by using HashMap
		for(String element : graph.vertexSet()){
			
			int vertex= Integer.parseInt(element);
			vertices.add(vertex);
			vertex_color.put(vertex, Color.white);
					
		}
		
		//Sorting
		Collections.sort(vertices);
		
		time = 0;
		
		for(Integer vertex : vertices){
			
				if(vertex_color.get(vertex)== Color.white){
					
					dfs(graph,  vertex);
					
				}
					
		}
		
		
		
	}
	
	
	
	public void dfs(WeightedGraph<String, DefaultWeightedEdge> graph, int vertex){
		time = time + 1;
		vertex_discover.put(vertex, time);
		
		vertex_color.put(vertex, Color.gray);
		
		for(Integer element : getNeighborSet(graph,vertex)){
			
			if(vertex_color.get(element)== Color.white){
				dfs(graph,element);
			}
			
		}
		time = time + 1;
		
		vertex_color.put(vertex, Color.black);
		vertex_finish.put(vertex, time);
		
		
		
		
	}
	
	
	
	
//	public int getMin(Set<String> set){
//		
//		int min=Integer.MAX_VALUE;
//		
//		for(String vertex: set){
//			
//			int element = Integer.parseInt(vertex);
//			
//			if( element < min){
//				min = element;
//			}
//			
//		
//		}
//		
//		return min;	
//		
//		
//	}
	
	//find the neighborSet of specific vertex
	public List<Integer> getNeighborSet(WeightedGraph<String, DefaultWeightedEdge> graph, int v){
		List <String> neighbor = new ArrayList <String> ();
		List <Integer> result = new ArrayList <Integer> ();
		
		for( DefaultWeightedEdge element : graph.edgesOf(String.valueOf(v))){
			if(graph.getEdgeSource(element).equals(String.valueOf(v)) ){
				neighbor.add(graph.getEdgeTarget(element));
			
							
			}else{
				neighbor.add(graph.getEdgeSource(element));
			}
		}
		
		for(String element: neighbor){
			result.add(Integer.parseInt(element));
		}
		
		Collections.sort(result);
		return result;
		
		
	}
	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
//		WeightedGraph<String, DefaultWeightedEdge> graph =
//		 new SimpleWeightedGraph <String, DefaultWeightedEdge>(DefaultWeightedEdge.class);
//		 String v1 = "1";
//		 String v2 = "2";
//		 String v3 = "3";
//		 String v4 = "4";
//		 String v5 = "5";
//		 String v6 = "6";
//		 graph.addVertex(v1);
//		 graph.addVertex(v2);
//		 graph.addVertex(v3);
//		 graph.addVertex(v4);
//		 graph.addVertex(v5);
//		 graph.addVertex(v6);
//		
//		 graph.addEdge(v3, v2);
//		 graph.addEdge(v3, v4);
//		 graph.addEdge(v3, v5);
//		 graph.addEdge(v1, v2);
//		 graph.addEdge(v4, v6);
//		 graph.addEdge(v5, v6);
//		 
//		 DeepFirstSearch dfs = new DeepFirstSearch();
//		 dfs.initial(graph);
//		 
//		 List<Map.Entry<Integer,Integer>> list = new ArrayList<Map.Entry<Integer,Integer>>(dfs.vertex_discover.entrySet());
//	     Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
//	          public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
//	               return o1.getValue().compareTo(o2.getValue());
//	          }
//	     });
//		 
//		System.out.print("[");
//		for(Map.Entry<Integer, Integer> map: list){
//			System.out.print(map.getKey()+ " ");
//		}
//		System.out.print("]");
		 
	}

}
